//
// Created by 16933 on 2022/11/21.
//

#include "Algorithm_Dijkstra.h"
int min_distance = GIGANTIC;
int min_distance_index =0;
/**
 * @brief 算法初始化
 * @param controler:算法控制器
 * @param
 * */
void Dijkstra_Init(DijkstraControler* controler,SystemControler* system_data)
{
    /**
     * 初始化：1.出发点是第一的已经确定最短路径的顶点
     *       2.更新与出发点有路径的顶点的最短路径和前驱顶点
     * */
     int distance_temp = 0;
     /* 获取需要使用的信息 */
    controler->mgraph = system_data->graph_data;
    controler->start_point = system_data->start_point;
    controler->end_point = system_data->end_point;
    for (int i = 0; i < MAX_VERTICES; ++i) {
        controler->distance_list[i] = 0;
        controler->confirmed_flag_list[i] = 0;
        controler->forerunner_list[i] = 0;
    }
    int node_num =  controler->mgraph->numNodes;
    /*顶点最短路径初始化为无穷*/
    for (int i = 0; i < node_num; ++i) {
        controler->distance_list[i+1] = GIGANTIC;         //0弃除不用 从1开始

    }

    /* 出发点是第一的已经确定最短路径的顶点,自己到自己的距离是0 */
    controler->latest_confirmed_node = controler->start_point;
    controler->distance_list[controler->start_point] = 0;
    controler->confirmed_flag_list[controler->start_point] = 1;     //起始点已经确定
    controler->forerunner_list[controler->start_point] = controler->start_point;
    /* 更新与出发点有路径的顶点的最短路径和前驱顶点 */
    Update_Distance_Predecessor(controler,controler->start_point);

}

/**
 * @brief 算法控制器释放
 * */
void Dijkstra_Relese(DijkstraControler* controler)
{

    controler->end_point = 0;
    controler->start_point = 0;
    controler->sum_distance = 0;
    for (int i = 0; i<sizeof(controler->route)/ sizeof(int); ++i) {
        controler->route[i] = 0;
    }
    for (int i = 0; i < sizeof(controler->distance_list)/sizeof(int); ++i) {
        controler->distance_list[i] = 0;
    }
}



/**
 * @brief 算法循环
 * @param controler:算法控制器
 * */
 void Dijkstra_Loop(DijkstraControler* controler)
{
     /**
      * 循环：1.从未确定最短路径的顶点中选取最短路径最小的顶点为新确定最短路径的顶点；
      *      2.更新与新确认顶点有路径的顶点的最短路径和前驱顶点。(如果新路径更短就更新，更长则不更新)
      *
      * 结束条件：所有的点都被确定过最短路径了即寻找完毕
      * */

     int min_distance = 0;
     int new_point = 0;
    while (!controler->confirmed_flag_list[controler->end_point])
    {
        /*从未确定最短路径的顶点中选取最短路径最小的顶点为新确定最短路径的顶点*/
        Update_Confirmed_Node(controler);

        /* 更新与新确认顶点有路径的顶点的最短路径和前驱顶点 */
        Update_Distance_Predecessor(controler,controler->latest_confirmed_node);

    }


}



/**
 * @brief 通过终点寻找最优路径
 * @param controler:算法控制器
 * */

void Dijkstra_Find_Path(DijkstraControler* controler)
{
    int node = controler->end_point;
    int i = 0;
    while (node != controler->start_point)
    {

        controler->route[i] = node;
        node = controler->forerunner_list[node];
        i++;
    }
    controler->route[i] = node;
    controler->sum_distance+=controler->distance_list[controler->end_point];

}



/**
 * @brief 在遍历相关数据的时候进行对比找出最小
 * */
 int Find_Min(int data,int index)
{

    if (min_distance == GIGANTIC)
    {
        min_distance = data;
        min_distance_index = index;
    } else
    {
        if (data<=min_distance)
        {
            if (data != GIGANTIC)
            {
                min_distance = data;
                min_distance_index = index;
            }

        }
    }

    return min_distance_index;
}


/**
 * @brief 更新与确认顶点有路径的顶点的最短路径
 * @param
 * */
 void Update_Distance_Predecessor(DijkstraControler* controler,int comfirmed_point)
{
     int node_num = controler->mgraph->numNodes;
     int distance_temp = 0;
    for (int i = 0; i < node_num; ++i)
    {
        distance_temp = controler->mgraph->arc[comfirmed_point][i+1];

        if ( distance_temp != 0)  //找到有路径的顶点的路径长度
        {
            //如果与confirmed_point有关的路径的最短距离比它原来的最短距离更小 就更新它
            if (distance_temp + controler->distance_list[comfirmed_point] < controler->distance_list[i+1] || controler->distance_list[i+1]==GIGANTIC)
            {
                controler->distance_list[i+1] =  distance_temp + controler->distance_list[comfirmed_point]; //更新最短距离
                Update_predecessor_node(controler,comfirmed_point,i+1);//更新前驱顶点
            }

        }


    }
}

/**
 * @brief  更新确认节点节点
 * */
void Update_Confirmed_Node(DijkstraControler* controler)
{
     int min_distance_index;
    for (int i = 0; i < controler->mgraph->numNodes; ++i)       //找最短路径最小的顶点
    {
        if (controler->confirmed_flag_list[i+1] != 1)
        {
            min_distance_index  = Find_Min(controler->distance_list[i+1],i+1);
            controler->latest_confirmed_node = min_distance_index;             //更新最新被确认的顶点
        }
    }
    min_distance = GIGANTIC;
    controler->confirmed_flag_list[controler->latest_confirmed_node] = 1;
}


/**
 * @brief 更新前驱节点
 * @param predecessor_node:前驱节点，一般为leatest_confirmed_node
 * @param node: 需要被更新前驱节点的节点
 * */

void Update_predecessor_node(DijkstraControler* controler,int predecessor_node,int node)
{
    controler->forerunner_list[node] = predecessor_node;
}